﻿/*
   Copyright 2013 Dmitry Bratus

   Licensed under the Apache License, Version 2.0 (the "License");
   you may not use this file except in compliance with the License.
   You may obtain a copy of the License at

       http://www.apache.org/licenses/LICENSE-2.0

   Unless required by applicable law or agreed to in writing, software
   distributed under the License is distributed on an "AS IS" BASIS,
   WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
   See the License for the specific language governing permissions and
   limitations under the License.
*/
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Collections;

namespace Flower.Actors
{
    public class ArrayHeap<T> : ICollection, IEnumerable<T>
    {
        private const int DEFAULT_CAPACITY = 10;

        private readonly IComparer<T> _comparer;
        private T[] _data;
        private int _count;

        internal T this[int i]
        {
            get
            {
                if (i >= _count) throw new IndexOutOfRangeException();

                return _data[i];
            }
        }

        public ArrayHeap(IComparer<T> comparer)
            : this(DEFAULT_CAPACITY, comparer)
        {
        }

        public ArrayHeap(int capacity, IComparer<T> comparer)
        {
            _comparer = comparer;
            _data = new T[capacity];
            _count = 0;
        }

        public int Count { get { return _count; } }

        public static int LevelBase(int level)
        {
            return (1 << level) - 1;
        }

        public static int LevelOf(int idx)
        {
            int lev = 0;
            int levBase = 1;
            int lim = idx + 1;

            while (levBase <= lim)
            {
                ++lev;
                levBase <<= 1;
            }

            return lev - 1;
        }

        public static int ParentIndex(int idx)
        {
            if (idx == 0) throw new ArgumentException("idx");

            int lev = LevelOf(idx);

            return LevelBase(lev - 1) + ((idx - LevelBase(lev)) >> 1);
        }

        public static int LeftChildIndex(int idx)
        {
            if (idx == 0) return 1;

            int lev = LevelOf(idx);

            return LevelBase(lev + 1) + ((idx - LevelBase(lev)) << 1);
        }

        public void Swap(int i1, int i2)
        {
            T tmp = _data[i1];
            _data[i1] = _data[i2];
            _data[i2] = tmp;
        }

        public T Peek()
        {
            if (_count == 0) throw new InvalidOperationException("The heap is empty.");

            return _data[0];
        }

        public void Add(T item)
        {
            if (_data.Length == _count)
            {
                var newData = new T[_count * 2];
                Array.Copy(_data, newData, _count);
                _data = newData;
            }

            var newIdx = _count++;

            _data[newIdx] = item;

            if (newIdx > 0)
            {
                while (true)
                {
                    int parentIdx = ParentIndex(newIdx);
                    T parent = _data[parentIdx];

                    if (_comparer.Compare(parent, item) > 0)
                    {
                        Swap(newIdx, parentIdx);
                        newIdx = parentIdx;

                        if (newIdx == 0) break;
                    }
                    else
                    {
                        break;
                    }
                }
            }
        }

        public T Pop()
        {
            if (_count == 0) throw new InvalidOperationException("The heap is empty.");

            var min = _data[0];

            _data[0] = _data[--_count];
            _data[_count] = default(T);

            if (_count > 1)
            {
                int parentIdx = 0;
                T parent = _data[0];

                while (true)
                {
                    int lchildIdx = LeftChildIndex(parentIdx);

                    if (lchildIdx >= _count) break;

                    int rchildIdx = lchildIdx + 1;

                    if (rchildIdx >= _count)
                    {
                        if (_comparer.Compare(parent, _data[lchildIdx]) > 0)
                        {
                            Swap(parentIdx, lchildIdx);
                            parentIdx = lchildIdx;
                        }
                        else
                        {
                            break;
                        }
                    }
                    else
                    {
                        T lchild = _data[lchildIdx];
                        T rchild = _data[rchildIdx];

                        if (_comparer.Compare(lchild, rchild) > 0)
                        {
                            if (_comparer.Compare(parent, rchild) > 0)
                            {
                                Swap(parentIdx, rchildIdx);
                                parentIdx = rchildIdx;
                            }
                            else
                            {
                                break;
                            }
                        }
                        else
                        {
                            if (_comparer.Compare(parent, lchild) > 0)
                            {
                                Swap(parentIdx, lchildIdx);
                                parentIdx = lchildIdx;
                            }
                            else
                            {
                                break;
                            }
                        }
                    }
                }
            }

            return min;
        }

        public T[] Steal(int count)
        {
            if (count > _count) throw new InvalidOperationException("Too many items to steal.");

            var stolen = new T[count];

            var newCount = _count - count;
            for (int i = newCount, j = 0; i < _count; ++i, ++j)
            {
                stolen[j] = _data[i];
                _data[i] = default(T);
            }

            _count = newCount;

            return stolen;
        }

        public void CopyTo(Array array, int index)
        {
            for (int i = 0, j = index; i < _count; i++, j++)
            {
                array.SetValue(_data[i], j);
            }
        }

        public bool IsSynchronized
        {
            get { return false; }
        }

        public object SyncRoot
        {
            get { return this; }
        }

        private IEnumerable<T> Enumerate()
        {
            int initialCount = _count;

            for (int i = 0; i < initialCount; i++)
            {
                yield return _data[i];

                if (_count != initialCount)
                {
                    throw new InvalidOperationException("Collection was modified; enumeration operation may not execute.");
                }
            }
        }

        public IEnumerator GetEnumerator()
        {
            return Enumerate().GetEnumerator();
        }

        IEnumerator<T> IEnumerable<T>.GetEnumerator()
        {
            return Enumerate().GetEnumerator();
        }
    }
}
